An integrated circuit (IC) comprises cells of similar and/or various sizes, and connections between or among the cells. A cell includes several pins interconnected by wires to pins of one or more other cells. A net includes a set of pins connected by wires in order to form connections between or among the pins. A set of nets, called a netlist, defines the connections of an IC. In other words, a netlist specifies a group of nets, which, in turn, specify the required interconnections between or among a set of pins.
Design engineers design IC's by transforming circuit descriptions of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (EDA) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.
EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectilinear lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes.
The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit components; (4) routing, which completes the interconnects between or among the circuit components; and (5) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a routing topology that includes an approximate routing path for the interconnect lines that are to connect the pins of the net. After the routing topology has been created, detailed routing creates specific individual routes for each net.
Due to the large number of nets in the netlist, it typically takes a long time for conventional routers to finish the connection task. In addition, the connections may be too numerous and/or overcrowded, such that conventional routers fail to finish the routing, particularly generating interconnections, without violating one or more routing constraints (e.g., design-rule constraints and performance constraints).